package me.mingshan.leetcode;

/**
 * https://leetcode.cn/problems/merge-nodes-in-between-zeros/description/
 *
 * 2181. 合并零之间的节点
 *
 * 给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的 开端 和 末尾 的节点都满足 Node.val == 0 。
 *
 * 对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。
 *
 *  返回修改后链表的头节点 head 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：head = [0,3,1,0,4,5,2,0]
 * 输出：[4,11]
 * 解释：
 * 上图表示输入的链表。修改后的链表包含：
 * - 标记为绿色的节点之和：3 + 1 = 4
 * - 标记为红色的节点之和：4 + 5 + 2 = 11
 * 示例 2：
 *
 *
 * 输入：head = [0,1,0,3,0,2,2,0]
 * 输出：[1,3,4]
 * 解释：
 * 上图表示输入的链表。修改后的链表包含：
 * - 标记为绿色的节点之和：1 = 1
 * - 标记为红色的节点之和：3 = 3
 * - 标记为黄色的节点之和：2 + 2 = 4
 *
 *
 * @author hanjuntao
 * @date 2025/7/28 0028
 */
public class L_2181_merge_nodes_in_between_zeros {

    public static void main(String[] args) {
        // 0,3,1,0,4,5,2,0
        ListNode node1 = new ListNode(0);
        ListNode node2 = new ListNode(3);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(0);
        ListNode node5 = new ListNode(4);
        ListNode node6 = new ListNode(5);
        ListNode node7 = new ListNode(2);
        ListNode node8 = new ListNode(0);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = node8;

        ListNode listNode = mergeNodes(node1);
        System.out.println(listNode); // 4->11

    }

    /**
     * 思路：
     *
     * 1. 创建一个虚拟节点，作为头节点，方便处理
     * 2. 循环链表，在没有遇到0节点时，将当前节点的值累加到sum中
     * 3. 如果遇到0，将上一次累计的sum，生成一个节点，并添加到结果链表中
     *
     * @param head
     * @return
     */
    public static ListNode mergeNodes(ListNode head) {
        ListNode newHead = null;
        ListNode newCurr = null;

        ListNode curr = head.next;

        int sum = 0;

        while (curr != null) {
            if (curr.val == 0) {
                ListNode listNode = new ListNode(sum);
                if (newHead == null) {
                    newHead = listNode;
                    newCurr = newHead;
                } else {
                    newCurr.next = listNode;
                    newCurr = newCurr.next;
                }
                sum = 0;
            } else {
                sum += curr.val;
            }

            curr = curr.next;
        }

        return newHead;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }

        static void print(ListNode head) {
            StringBuilder sb = new StringBuilder("[");
            for (ListNode current = head; current != null; current = current.next) {
                sb.append(current.val + ", ");
            }

            int len = sb.length();
            System.out.println(sb.delete(len - 2, len).append("]").toString());
        }
    }
}
